// ==================================================
// Programmer:  Jonathan Landrum
// Date:        29 March 2012
// ==================================================
// Program:     combinations.cpp
// Purpose:     Calculates the number of combinations
//		that can be made with given input of
//		discrete items.
// Assumptions: 1.) Input is an integer. Real input
//		    will be cast to the next lowest
//		    integer.
//		2.) Input is positive. Negative
//		    input and text input will simply
//		    return 0.
// Issues:      1.) The functions pascal() and
//		    factorial() slow down
//		    significantly for input greater
//		    than 23 due to the fact that they
//		    use recursion to calculate their
//		    results.
// ==================================================

#include <iostream>
#include <string>

using namespace std;


// --------------------------------------------------
// Function Prototypes
// --------------------------------------------------
long int factorial (long int in);
long int pascal    (long int row, long int column);


// --------------------------------------------------
// main():
// Calls factorial() and returns results.
// --------------------------------------------------
int main () {
	
	// Variables
	float n, r;
	int   group, choose;
	long int result = 1;
	
	// Introduce the program
	cout << endl;
	cout << "------------------------------------" << endl;
	cout << "-     Combinatorics Calculator     -" << endl;
	cout << "------------------------------------" << endl;
	cout << endl;
	cout << "              /n\\      n!" << endl;
	cout << "        nCr = | | = --------" << endl;
	cout << "              \\r/   r!(n-r)!" << endl;
	cout << endl;
	cout << "This program calculates how many" << endl;
	cout << "combinations can be made of a given" << endl;
	cout << "number of choices, and a given sized" << endl;
	cout << "group from which to choose." << endl;
	
	// Get user input
	try {
		do {
			cout << endl;
			
			cout << "Size of the group (n): ";
			
			cin  >> n;
		} while (n < 0);
		
		do {
			cout << endl;
			
			cout << "Number of choices (r): ";
			
			cin  >> r;
		} while (r < 0);
		
		cout << endl;
		
		group  = (int)n;
		choose = (int)r;
	}
	catch (...) {
		cout << "Error: << Unexpected Input >>" << endl;
		return (-1);
	}
	
	if (choose > group) {
		cout << 0 << endl << endl;
		return (0);
	}
	
	result = 1;
	
	for (int i = 1; i <= choose; ++i)
		result *= ((float)(group - choose + i)/i);
	
	cout << "Product:\t" << result << endl << endl;
	
	result = group;
	
	for (int i = 1; i <= choose - 1; ++i)
		result *= (group - i);
	
	cout << "Division:\t" << (result/factorial(choose)) << endl << endl;
	
	cout << "Pascal:\t\t" << pascal(group + 1, choose + 1) << endl << endl;
	
	cout << "Factorial:\t" << (factorial(group)/(factorial(choose) * factorial(group - choose))) << endl << endl;
	
	return (0);
} // End main


// --------------------------------------------------
// factorial():
//
// Recursive function.
// Returns int, accepts (int in).
// 
// Calculates the factorial of the given number.
// --------------------------------------------------
long int factorial (long int in) {
	long int result = 0;
	
	if ((in == 0 ) || (in == 1))
		result = 1;
	else if (in == 2)
		result = 2;
	else
		result = in * factorial(in - 1);
	
	return result;
} // End factorial


// --------------------------------------------------
// pascal():
//
// Recursive function.
// Returns long int
// Accepts (long int row, long int column).
// 
// Calculates the value of the number at the 
// specified row and column of Pascal's Triangle.
// --------------------------------------------------
long int pascal (long int row, long int column) {
	long int result = 0;
	
	if ((column == 1) || (row == column))
		result = 1;
	else
		result = pascal(row - 1, column - 1) + pascal(row - 1, column);
	
	return result;
}